//
//  Problem746.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

/*
 746. 使用最小花费爬楼梯
 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。


 示例 1：
     输入：cost = [10, 15, 20]
     输出：15
     解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
     输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
     输出：6
     解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
  
 提示：
     cost 的长度范围是 [2, 1000]。
     cost[i] 将会是一个整型数据，范围为 [0, 999] 。
 */

import UIKit

@objcMembers class Problem746: NSObject {
    func solution() {
        print(minCostClimbingStairsClearAlloc([10, 15, 20]))
        print(minCostClimbingStairsClearAlloc([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[len]
     2: dp[i]: 登上第i阶梯需要花费的值
     3: dp[i] 2个状态：
        从dp[i-1]登录的，dp[i-1] + cost[i-1]
        从dp[i-2]登录的, dp[i] = dp[i-2] + cost[i-2]
        dp[i] = min()
     */
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        if cost.count <= 1 {
            return 0
        }
        
        var dp = Array(repeating: 0, count: cost.count + 1)
        dp[0] = 0       // 到达cost[0], 从台阶0开始，执行1步
        dp[1] = 0       // 到达cost[1], 从台阶0开始，执行2步
        for i in 2...cost.count {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        }
        print(dp)

        return dp[cost.count]
    }
    
    /*
     优化 dp[i]只与dp[i-1]和dp[i-2]有关
     */
    func minCostClimbingStairsClearAlloc(_ cost: [Int]) -> Int {
        if cost.count <= 1 {
            return 0
        }
        
        var first = 0     // 到达cost[0], 从台阶0开始，执行1步
        var second = 0    // 到达cost[1], 从台阶0开始，执行2步
        for i in 2...cost.count {
            let value = min(first + cost[i-1], second + cost[i-2])
            second = first
            first = value
        }

        return first
    }
}
